﻿using System;
using System.Collections.Generic;
using System.Drawing;

namespace ProblemsSet
{
    public class Problem_152 : BaseProblem
    {
        const int max = 80;

        public override object GetResult()
        {
            var res = GetSetsForPrime();
            var lst = MathLogic.GetPrimeList(max, true);
            lst.Remove(2);
            lst.Remove(3);

            var prms = new List<long>();
            foreach (var re in res)
            {
                prms.Add(re.Key);
                lst.Remove(re.Key);
            }
            prms.Sort();
            var ans = new List<List<long>>();

            RecLists(ref res, 0, ref prms, new List<long>(), ref ans);

            var dc = new Dictionary<Rational, List<List<long>>>();
            foreach (var an in ans)
            {
                var rs = GetSumArr(lst, an);
                if (rs <= 0)
                    continue;
                if (!dc.ContainsKey(rs))
                    dc.Add(rs, new List<List<long>>());
                dc[rs].Add(an);
            }
            var rss = 0;
            
            var qqq = new Dictionary<Rational, List<List<long>>>();
            RecFinLists(ref qqq, new Rational(1,2), new List<long>(), 2);

            foreach (var pair in qqq)
            {
                if (dc.ContainsKey(pair.Key))
                    rss += dc[pair.Key].Count*pair.Value.Count;
            }

            return rss;
        }

        private static void RecFinLists(ref Dictionary<Rational, List<List<long>>> answer, Rational cur, List<long> current, long ind)
        {
            if (cur < 0) return;
            if (!answer.ContainsKey(cur))
                answer.Add(cur, new List<List<long>>());
            var ex = false;
            foreach (var list in answer[cur])
            {
                if (MathLogic.IsEqual(current, list))
                {
                    ex = true;
                    break;
                }
            }
            if (!ex)
                answer[cur].Add(current);
            for (long i = ind; i <= max; i++)
            {
                if (!IsNeed(i))
                    continue;
                var tmp = new Rational(1, i*i);
                var tt = new List<long>(current);
                tt.Add(i);
                RecFinLists(ref answer, cur-tmp, tt, i+1);
            }
        }

        private static bool IsNeed(long val)
        {
            var lst = MathLogic.GetPrimeFactors(val);
            foreach (var pair in lst)
            {
                if (pair.Key != 2 && pair.Key !=3)
                    return false;
            }
            return true;
        }

        private static void RecLists(ref Dictionary<long, List<List<long>>> init, long cur, ref List<long> keys, List<long> current, ref List<List<long>> answer)
        {
            long next = -1;
            foreach (var l in keys)
            {
                if (l > cur)
                {
                    next = l;
                    break;
                }
            }
            if (next == -1)
            {
                if (current.Count <= 0)
                    return;
                foreach (var list in answer)
                {
                    if (MathLogic.IsEqual(list, current))
                        return;
                }
                current.Sort();
                answer.Add(current);
                return;
            }
            var tmp = new List<long>(current);
            RecLists(ref init, next, ref keys, tmp, ref answer);
            foreach (var list in init[next])
            {
                var hs = new HashSet<long>(current);
                hs.UnionWith(new HashSet<long>(list));
                RecLists(ref init, next, ref keys, new List<long>(hs), ref answer);
            }
        }

        private static Rational GetSumArr(ICollection<long> primes, IEnumerable<long> values)
        {
            Rational sm = 0;
            var mx = new Rational(1, 2);
            var dct = new Dictionary<long, Rational>();
            foreach (var l in values)
            {
                var lst = MathLogic.GetPrimeFactors(l);
                var ad = new Rational(1, l*l);
                sm += ad;
                if (sm > mx)
                    return -1;
                foreach (var pair in lst)
                {
                    if (pair.Key == 2 || pair.Key == 3)
                        continue;
                    if (primes.Contains(pair.Key))
                        return -1;
                    if (!dct.ContainsKey(pair.Key))
                        dct.Add(pair.Key, 0);
                    dct[pair.Key] += ad;
                }
            }
            foreach (var pair in dct)
            {
                if (pair.Value.Denomirator % pair.Key == 0)
                    return -1;
            }
            return sm;
        }

        private static Dictionary<long, List<List<long>>> GetSetsForPrime()
        {
            var res = new Dictionary<long, List<List<long>>>();
            var lst = MathLogic.GetPrimeList(max, true);
            lst.Remove(2);
            lst.Remove(3);
    
            FormeEq(ref res, 0, new List<long>(), 1, ref lst);

            return res;
        }

        private static void FormeEq(ref Dictionary<long, List<List<long>>> answer, Rational cur, IList<long> current, int indx, ref List<long> primes)
        {
            var mx = new Rational(1, 2);
            if (current.Count > 1)
            {
                foreach (var l in primes)
                {
                    if (current[current.Count-1]*l > max)
                        break;
                    if (cur.Nomirator%(l*l) != 0) continue;
                    if (cur.Denomirator%l == 0) continue;
                    var mlt = new List<long>(current);
                    for (var i = 0; i < mlt.Count; i++ )
                    {
                        mlt[i] *= l;
                    }
                    if (!answer.ContainsKey(l))
                        answer.Add(l, new List<List<long>>());
                    var ex = false;
                    foreach (var list in answer[l])
                    {
                        if (!MathLogic.IsEqual(list, mlt)) continue;
                        ex = true;
                        break;
                    }
                    if (!ex)
                    {
                        answer[l].Add(mlt);
                    }
                }
            }
            
            for (var i = indx; i <= max/5; i++)
            {
                var tmp = new Rational(1, i * i);
                var lst = new List<long>(current) { i };
                FormeEq(ref answer, cur + tmp, lst, i + 1, ref primes);
            }
        }

        public override string Problem
        {
            get
            {
                return @"There are several ways to write the number 1/2 as a sum of inverse squares using distinct integers.

For instance, the numbers {2,3,4,5,7,12,15,20,28,35} can be used:



In fact, only using integers between 2 and 45 inclusive, there are exactly three ways to do it, the remaining two being: {2,3,4,6,7,9,10,20,28,35,36,45} and {2,3,4,6,7,9,12,15,28,30,35,36,45}.

How many ways are there to write the number 1/2 as a sum of inverse squares using distinct integers between 2 and 80 inclusive?";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 301;
            }
        }
    }
}
